#include "mem.h"

namespace VirtualR {

// const uint32_t MAX_HEIGHT = 12;
#define MAX_HEIGHT 12
SkipList::SkipList() {
  // new head 的时候new为最大height, height表示真实的高度
  head = new Node_t("", "", MAX_HEIGHT);
  max_height_ = 1;
  head->height_ = 1;
}

SkipList::~SkipList() {
  if (head != nullptr) {
    delete head;
  }

}

void SkipList::get_random_height(uint32_t &height) {
  int32_t num = 4;
  height = 1;
  while (height < MAX_HEIGHT && rand() % 4 == 0) {
    height++;
  }
}

Node_t *SkipList::find_lower_or_equal_node(std::string key, Node_t **ans) {
  Node_t *res = head, *prev = head;
  for (int i = max_height_ - 1; i >= 0; i--) {
    while (res != nullptr && res->key_ <= key) {
      prev = res;
      res = res->next[i];
    }
    res = prev;
    ans[i] = prev;
  }
  return prev;
}

bool SkipList::put(std::string key, std::string value) {
  Node_t *prev[max_height_];
  Node_t *prev_ = find_lower_or_equal_node(key, prev);
  if (prev_ == nullptr) {
    // assert(false);
    return false;
  }
  uint32_t node_height = 1;
  get_random_height(node_height);
  Node_t *new_node = new Node_t(key, value, node_height);
  if (max_height_ < node_height) {
    for (int i = node_height - 1; i >= max_height_; i--) {
      new_node->prev[i] = head;
    }

    for (int i = 0; i < max_height_; i++) {
      Node_t *tmp = prev[i];
      new_node->next[i] = tmp->next[i];
      new_node->prev[i] = tmp;

      Node_t *tmp_next = tmp->next[i];
      tmp->next[i] = new_node;
      if (tmp_next != nullptr) {
        tmp_next->prev[i] = new_node;
      }
    }

    max_height_ = node_height;
    head->height_ = max_height_;
  } else {
    for (int i = 0; i < node_height; i++) {
      Node_t *tmp = prev[i];
      new_node->next[i] = tmp->next[i];
      new_node->prev[i] = tmp;

      Node_t *tmp_next = tmp->next[i];
      tmp->next[i] = new_node;
      if (tmp_next != nullptr) {
        tmp_next->prev[i] = new_node;
      }
    }
  }
  entry_++;
  if (!value.empty()) {
    // uint32_t + key.size() + uint64_t + value.size()
    total_size_ += key.size() + value.size() + sizeof(uint64_t) + sizeof(uint32_t);
  } else {
    total_size_ -= value.size();
  }
  return true;
}

bool SkipList::get(std::string key, std::string &value) {
  Node_t *prev[max_height_];
  Node_t *tmp = find_lower_or_equal_node(key, prev);
  if (tmp == nullptr) {
    value = "";
    return false;
  }
  if (tmp->key_ == key) {
    value = tmp->value_;
    if (value == "") {
      return false;
    }
    return true;
  }
  value = "";
  return false;
}

bool SkipList::del(std::string key) {
  Node_t *prev[max_height_];
  Node_t *tmp = find_lower_or_equal_node(key, prev);

  if (tmp == nullptr || tmp->key_ != key) {
    return false;
  }
  bool ret = false;
  if ((ret = put(key, ""))) {
    entry_--;
  }
  return ret;
}

bool SkipList::Iterator::has_next() {
  return node_->next[0] != nullptr;
}

void SkipList::Iterator::next() {
  node_ = node_->next[0];
}

void SkipList::Iterator::prev() {
  node_ = node_->prev[0];
}

std::string SkipList::Iterator::key() {
  return node_->key_;
}

std::string SkipList::Iterator::value() {
  return node_->value_;
}

SkipList::Iterator *SkipList::iterator() {
  return new SkipList::Iterator(this, this->head);
}

bool SkipList::Iterator::valid() {
  return node_ != nullptr;
}

uint64_t SkipList::space() {
  // meta_size + total_count
  return total_size_ + sizeof(uint64_t) + sizeof(uint64_t);
}

} // namespace VirtualR